package com.zk.algorithm;

import com.zk.algorithm.sort.QuickSort;

public class QuickSelectKthSmallest {

    public static void main(String...args) {
        int[] arr = new int[]{ 12, 3, 5, 7, 4, 19, 26 };
        System.out.println(new QuickSelectKthSmallest().kthSmallest(arr, 0, arr.length - 1, 7));
    }

    // k: 范围 [1, n]
    int kthSmallest(int arr[], int left, int right, int k) {
        // If k is smaller than number of elements in array
        if (k > 0 && k <= right - left + 1) {
            // Partition the array around a random element and
            // get position of pivot element in sorted array
            int pos = QuickSort.partition(arr, left, right);

            // If position is same as k
            if (pos-left == k-1)
                return arr[pos];

            // If position is more, recur for left subarray
            if (pos-left > k-1)
                return kthSmallest(arr, left, pos-1, k);

            // Else recur for right subarray
            return kthSmallest(arr, pos+1, right, k-pos+left-1);
        }

        // If k is more than number of elements in array
        return Integer.MAX_VALUE;
    }

}
